package me.leetcodepractice;

public class E11Leetcode142 {
    // 找环的入口
    public ListNode detectCycle(ListNode head) {
        ListNode h = head; // 兔子
        ListNode t = head; // 龟
        while (h != null && h.next != null) {
            t = t.next;
            h = h.next.next;
            if (h == t) { // 第一次相遇
                // 进入第二阶段
                t = head;
                while (true) {
                    if (h == t) { // 第二次相遇
                        return t; // 返回t,h都可以
                    }
                    h = h.next;
                    t = t.next;
                }
            }
        }
        return null;
    }

    public static void main(String[] args) {
        ListNode n5 = new ListNode(5, null);
        ListNode n4 = new ListNode(4, n5);
        ListNode n3 = new ListNode(3, n4);
        ListNode n2 = new ListNode(2, n3);
        ListNode n1 = new ListNode(1, n2);

        n5.next = n3;
        ListNode listNode = new E11Leetcode142().detectCycle(n1);
        System.out.println(listNode.val);
    }
}
